# knn_step2_algorithm.py
import numpy as np
import pandas as pd
from sklearn.datasets import load_iris
from collections import Counter

print("=== 第2题步骤2: KNN算法原理和实现 ===")

print("""
🎯 KNN算法原理:

K最近邻(K-Nearest Neighbors)算法是一种简单的监督学习算法，用于分类和回归。

核心思想: "物以类聚" - 一个样本的类别可以由其邻居的类别来决定。

算法步骤:
1. 计算测试样本与所有训练样本的距离
2. 选择距离最近的k个训练样本（k个邻居）
3. 统计这k个邻居的类别分布
4. 将出现次数最多的类别作为测试样本的预测类别

三要素:
- k值选择: 控制模型的复杂度
- 距离度量: 通常使用欧氏距离
- 分类决策规则: 多数投票法
""")

class SimpleKNN:
    def __init__(self, k=3):
        """
        初始化KNN分类器
        
        参数:
        k: 邻居数量，默认值为3
        """
        self.k = k
        self.X_train = None
        self.y_train = None
        
    def fit(self, X, y):
        """
        训练KNN分类器（实际上只是存储数据）
        
        参数:
        X: 训练特征，形状为 (n_samples, n_features)
        y: 训练标签，形状为 (n_samples,)
        """
        self.X_train = X
        self.y_train = y
        print(f"✅ 训练完成！存储了 {len(X)} 个训练样本")
        
    def euclidean_distance(self, x1, x2):
        """
        计算两个样本之间的欧氏距离
        
        参数:
        x1, x2: 两个样本的特征向量
        
        返回:
        欧氏距离
        """
        return np.sqrt(np.sum((x1 - x2) ** 2))
    
    def predict_single(self, x):
        """
        预测单个样本的类别
        
        参数:
        x: 单个样本的特征向量
        
        返回:
        预测的类别
        """
        # 计算与所有训练样本的距离
        distances = []
        for i, x_train in enumerate(self.X_train):
            dist = self.euclidean_distance(x, x_train)
            distances.append((dist, self.y_train[i]))
        
        # 按距离排序，选择前k个最近的邻居
        distances.sort(key=lambda x: x[0])
        k_nearest = distances[:self.k]
        
        # 统计k个邻居的类别
        k_nearest_labels = [label for _, label in k_nearest]
        most_common = Counter(k_nearest_labels).most_common(1)
        
        return most_common[0][0]
    
    def predict(self, X):
        """
        预测多个样本的类别
        
        参数:
        X: 测试特征，形状为 (n_samples, n_features)
        
        返回:
        预测的类别数组
        """
        predictions = []
        for i, x in enumerate(X):
            if i % 10 == 0:  # 进度显示
                print(f"  预测进度: {i}/{len(X)}")
            pred = self.predict_single(x)
            predictions.append(pred)
        return np.array(predictions)
    
    def accuracy(self, y_true, y_pred):
        """
        计算分类准确率
        
        参数:
        y_true: 真实标签
        y_pred: 预测标签
        
        返回:
        准确率
        """
        return np.sum(y_true == y_pred) / len(y_true)

# 测试KNN算法
def test_knn_implementation():
    print("\n🧪 测试KNN算法实现...")
    
    # 创建简单的测试数据
    print("创建测试数据...")
    X_train = np.array([
        [1, 2],
        [1.5, 1.8],
        [5, 8],
        [8, 8],
        [1, 0.6],
        [9, 11]
    ])
    y_train = np.array([0, 0, 1, 1, 0, 1])
    
    X_test = np.array([
        [1.2, 1.9],
        [7, 9]
    ])
    y_test = np.array([0, 1])
    
    print("训练数据:")
    for i in range(len(X_train)):
        print(f"  样本{i+1}: 特征{X_train[i]} -> 类别{y_train[i]}")
    
    print("\n测试数据:")
    for i in range(len(X_test)):
        print(f"  样本{i+1}: 特征{X_test[i]} -> 真实类别{y_test[i]}")
    
    # 使用KNN进行分类
    knn = SimpleKNN(k=3)
    knn.fit(X_train, y_train)
    
    predictions = knn.predict(X_test)
    
    print("\n📊 预测结果:")
    for i in range(len(X_test)):
        print(f"  测试样本{i+1}: 预测类别={predictions[i]}, 真实类别={y_test[i]}")
    
    accuracy = knn.accuracy(y_test, predictions)
    print(f"✅ 测试准确率: {accuracy:.2f}")

# 主程序
try:
    # 测试算法实现
    test_knn_implementation()
    
    print("\n" + "="*50)
    print("✅ KNN算法实现完成！")
    print("="*50)
    print("\n主要功能:")
    print("1. ✅ 欧氏距离计算")
    print("2. ✅ 最近邻搜索")
    print("3. ✅ 多数投票分类")
    print("4. ✅ 准确率计算")
    print("5. ✅ 批量预测")
    
except Exception as e:
    print(f"❌ 出错: {e}")
    import traceback
    traceback.print_exc()

input("\n按 Enter 键继续下一步...")
